#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL MOD = 1e9;
const LL MAXN = 6e5+7;
int Sum[33][MAXN];
int a[MAXN];
LL p;
int main(int argc, char** argv) {

#ifdef hai
    freopen("in.txt", "r", stdin);
#endif

    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        a[0] = 0;
        for (int i=1; i<=n; ++i) {
            scanf("%lld", a+i);
        }
        sort(a, a+n+1);
        LL Max = a[n];
        for (int i=1; i<=32; ++i) {
            Sum[i][0] = 0;
            for (int j=1; j<=n; ++j) {
                Sum[i][j] = (Sum[i][j-1] + a[j]/i % MOD) % MOD;
            }
        }
        LL res = 0;
        for (int i=1; i<=m; ++i) {
            scanf("%lld", &p);
            LL t = 0;
            LL last = 0;
            for (int j=1, k=1; k<=32; ++k) {
                if (j > Max / p) j = Max + 23;
                else j = j * p;
                LL en = upper_bound(a+last, a+n+1, j) - a;
                --en;
                if (en <= last) continue;
                t = (t + (Sum[k][en] - Sum[k][last]) % MOD) % MOD;
                t = (t + MOD) % MOD;
                last = en;
            }
            res = (res + i*t) % MOD;
        }
        printf("%lld\n", res);
    }
    return 0;
}
